P8054 题解

题目链接

我们只需尽可能的在区间 (1,n)(1,n) 内寻找质因子数量最多的数,再与 nn 的质因子数量比较即可。

考虑到 2k2^k 增长速度相比于其他质数 pkp^k 要慢,而对于和 2k2^k 大小相近的数,他们的质因子个数不可能比 2k2^k 要多。

我们可以感性理解这一件事情,于是我们就得到了第一个结论:

  • 在区间 (1,n)(1,n) 中,质因子个数最多的数为最大的形如 2k2^k 的数,即找到 2k<n2k+12^k \lt n \le 2^{k+1}

这一件事情可以在 O(logn)O(\log n) 的时间内做到。

然后就可以去比较 nn 的质因子个数与 kk 的大小了。

由于 n1018n \le 10^{18},分解质因数 O(n)O(\sqrt{n}) 的方式肯定是不可行的,那我们便使用一些奇技淫巧更高端的技巧。

我们考虑 nn 的一些特殊情况:

  1. nn 为奇数时,nn 中不含有质因子 22,此时我们可以感性理解一下,要想用奇质数乘出大小差不多的数,用到的质数个数会更少,所以 nn 的质因子个数必定小于 kk,即 f(n)<kf(n)<k

  2. n=2k+1n=2^{k+1} 时,此时虽然 2k2^k 已经是最大的了,但 nn 中有 k+1k+1 个质因子,所以 nn 的质因子个数大于 kk ,即 f(n)>kf(n)>k

  3. n=2k1×3n=2^{k-1} \times 3 时,此时 nn 正好介于 2k2^k2k+12^{k+1} 之间,但质因子个数也是 kk,故 f(n)=kf(n)=k

  4. 对于其他的偶数 nn,我们可以用第一类中的方法类似理解一下,质因子个数应该也是小于 kk 的,即 f(n)<kf(n)<k

综上所述,我们便可以用特判的方法过掉这一道题了,时间复杂度 O(Tlogn)O(T\log n)

还有就是注意一些细节,比如左移记得要用 long long

Code

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        long long n; scanf("%lld", &n);
        int k = 0;
        while (1LL << (k + 1) < n) k++;
        if (n >= 5 && n % 2 == 1) puts("1");
        else if (n % 3 == 0 && 1LL << (k - 1) == n / 3) puts("0");
        else if (n % 2 == 0 && 1LL << (k + 1) == n) puts("0");
        else puts("1");
    }
}
赞赏